package com.fengkai.filepost.pdfoutstream.test.ODsolutions;


import org.apache.commons.lang3.time.StopWatch;

import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.logging.Level;

/**
 * @author Fengkai
 * @creat 2023/4/18
 * 小明有 n 块木板，第 i ( 1 ≤ i ≤ n ) 块木板长度为 ai。
 * 小明买了一块长度为 m 的木料，这块木料可以切割成任意块，
 * 拼接到已有的木板上，用来加长木板。
 * 小明想让最短的木板尽量长。
 * 请问小明加长木板后，最短木板的长度可以为多少？
 * 输入描述
 * 输入的第一行包含两个正整数，n(1≤n≤10^3),m(1≤m≤10^6)
 * n表示木板数，m表示木板长度。输入的第二行包含n个正整数，a1,a2,...an(1≤ai≤10^6)。
 * 输出描述
 * 输出的唯一一行包含一个正整数，表示加长木板后，最短木板的长度最大可以为多少？
 * 示例一：
 * 输入：
 * 5 3
 * 4 5 3 5 5
 * 输出：
 * 5
 * 说明：
 * 给第1块木板长度增加1，给第3块木板长度增加2后，
 * 这5块木板长度变为[5,5,5,5,5]，最短的木板的长度最大为5。
 */
public class LongestWoodLength {
    public static void main (String[] args) {
//        int[] ints = {4, 5, 3, 5, 5};
//        System.out.println(longestWoodLength(2, ints));
        for (int i = 0; i < 500; i++) {
            StopWatch stopWatch = new StopWatch();
            StopWatch stopWatch2 = new StopWatch();
            int v = (int) (Math.random() * 1000 + 1);
            int[] ints = new int[v];
            for (int j = 0; j < v; j++) {
                int length = (int) (Math.random() * 100000 + 1);
                ints[j] = length;
            }
            int m = (int) (Math.random() * 100000 + 1);
            stopWatch.start();
            longestWoodLength(m, ints);
            stopWatch.stop();
            System.out.print(stopWatch.getTime());

            System.out.print("    ");
            stopWatch2.start();
            hisMethod(m, ints);
            stopWatch2.stop();
            System.out.print(stopWatch2.getTime());
            System.out.println();
        }

    }

    public static int longestWoodLength (int m, int[] sizes) {
        PriorityQueue<Integer> integers = new PriorityQueue<>();
        for (int size : sizes) {
            integers.add(size);
        }
        for (int i = 0; i < m; i++) {
            Integer poll = integers.poll();
            integers.add(++poll);
        }

        return integers.peek();
    }

    public static int hisMethod (int m, int[] sizes) {
        HashMap<Integer, Integer> woods_count = new HashMap<>();
        for (int i = 0; i < sizes.length; i++) {
            if (woods_count.containsKey(sizes[i])) {
                woods_count.put(sizes[i], woods_count.get(sizes[i]) + 1);
            } else {
                woods_count.put(sizes[i], 1);
            }
        }

        // 用木板的长度作为优先级队列的排序键 <length, count>
        PriorityQueue<Integer[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (Integer length : woods_count.keySet()) {
            pq.offer(new Integer[]{length, woods_count.get(length)});
        }

        while (m > 0) {
            //特殊情况, 只有一种长度
            if (pq.size() == 1) {
                Integer[] wood_kind = pq.poll();
                System.out.println(wood_kind[0] + m / wood_kind[1]);
                return wood_kind[0] + m / wood_kind[1];
            } else {
                Integer[] wood_kind_1 = pq.poll();
                Integer[] wood_kind_2 = pq.peek();

                int diff = wood_kind_2[0] - wood_kind_1[0];
                int total = diff * wood_kind_1[1];

                if (total > m) {
                    return wood_kind_1[0] + m / wood_kind_1[1];
                } else if (total == m) {
                    return wood_kind_2[0];
                } else {
                    m -= total;
                    wood_kind_2[1] += wood_kind_1[1];
                }
            }


        }
        return pq.peek()[0];
    }
}
